package Tree.HuffmanTree;

import java.util.*;

public class HuffmanTree {
    private HuffmanTreeNode root;
    List<HuffmanTreeNode> list = new ArrayList<>();
    public HuffmanTree() {
    }

    public HuffmanTree(String text) {
        Map<Character, Integer> characterIntegerMap = StringToInt(text);
        for (Map.Entry<Character, Integer> map : characterIntegerMap.entrySet()) {
            list.add(new HuffmanTreeNode(map.getKey(), map.getValue()));
        }
        createHuffman(list);
    }

    private void createHuffman(List<HuffmanTreeNode> list){
        while (list.size() > 1){
            Collections.sort(list);
            HuffmanTreeNode left = list.get(0);
            HuffmanTreeNode right = list.get(1);
            HuffmanTreeNode parent = new HuffmanTreeNode('\0',left.weight+right.weight,left,right);
            list.remove(0);
            list.remove(0);//此处由于移除了第一个结点，因此原本的第二个结点为现在的第一个结点
            list.add(parent);
        }
        root = list.get(0);
    }

    private Map<Character,Integer> StringToInt(String text){
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0;i<text.length();i++){
            map.put(text.charAt(i),map.getOrDefault(text.charAt(i),0)+1);
        }
        return map;
    }

    public void preorder() {
        preorder(root);
        System.out.println();
    }

    private void preorder(HuffmanTreeNode p) {
        if (p != null) {
            System.out.println(p);
            preorder(p.left);
            preorder(p.right);
        }
    }


    public Map<Character,String> getHuffmanCode(){
        Map<Character,String> HuffmanCode = new HashMap<>();
        getHuffmanCode(root.left,HuffmanCode,"0");
        getHuffmanCode(root.right,HuffmanCode,"1");
        return HuffmanCode;
    }

    public void getHuffmanCode(HuffmanTreeNode node,Map<Character,String> HuffmanCode,String compression){
        if (node!=null){
            if (node.isLeaf()){
                HuffmanCode.put(node.data,compression);
                compression = "";
            }
            getHuffmanCode(node.left,HuffmanCode,compression+"0");
            getHuffmanCode(node.right,HuffmanCode,compression+"1");
        }
    }

    public String TextToHuffmanCode(String text){
        String Huffmancode = "";
        Map<Character, String> huffmanCode = getHuffmanCode();
        for (int i=0;i<text.length();i++){
            Huffmancode += huffmanCode.get(text.charAt(i));
        }
        return Huffmancode;
    }

    public String decode(String text){
        String decode = "";
        HuffmanTreeNode p = root;
        for (int i=0;i<text.length();i++){
            if (text.charAt(i) == '0')p=p.left;
            if (text.charAt(i) == '1')p=p.right;
            if (p.isLeaf()){
                decode += p.data;
                p = root;
            }
        }
        return decode;
    }
}
